package Maze;

import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.GridLayout;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Timer;
import java.util.TimerTask;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JOptionPane;
import javax.swing.JPanel;

public class Maze extends JFrame
  implements ActionListener
{
  private JPanel panel;
  private JPanel northPanel;
  private JPanel centerPanel;
  private MazeGrid[][] grid;
  private JButton restart;
  private JButton dostart;
  private int rows;
  private int cols;
  private List<String> willVisit;
  private List<String> visited;
  private LinkedList<String> comed;
  private long startTime;
  private long endTime;
  int comeX = 0;
  int comeY = 0;

  public Maze()
  {
    this.rows = 25;              //定义该迷宫的高度
    this.cols = 25;              //定义该迷宫的宽度
    this.willVisit = new ArrayList();
    this.visited = new ArrayList();
    this.comed = new LinkedList();
    init();
    setTitle("回溯法--走迷宫");
    add(this.panel);
    pack();
    setVisible(true);
    setDefaultCloseOperation(3);
  }


  //初始化迷宫的frame
  public void init() {
    this.panel = new JPanel();
    this.northPanel = new JPanel();
    this.centerPanel = new JPanel();
    this.panel.setLayout(new BorderLayout());
    this.restart = new JButton("重新生成迷宫");
    this.dostart = new JButton("开始走迷宫");
    this.grid = new MazeGrid[this.rows][this.cols]; //实例化定义的grid数组，类型为MazeGrid

    this.centerPanel.setLayout(new GridLayout(this.rows, this.cols, 1, 1));//设置布局
    this.centerPanel.setBackground(new Color(0, 0, 0));//设置背景颜色
    this.northPanel.add(this.restart);
    this.northPanel.add(this.dostart);

    this.dostart.addActionListener(this);
    this.restart.addActionListener(this);
    for (int i = 0; i < this.grid.length; i++) {
      for (int j = 0; j < this.grid[i].length; j++)
        if ((j % 2 == 0) && (i % 2 == 0))
          this.grid[i][j] = new MazeGrid(true, 20, 20);
        else
          this.grid[i][j] = new MazeGrid(false, 20, 20);
    }
    /*
     * 这里的i是表示的该迷宫的纵坐标，j是代表的该迷宫的横坐标，这里的循环的功能过程如下：
     * 最初的位置是在0，0位置，当第一次循环的时候，i=0,j=0，此时i%2==0,j%2==0,所以此时
     * 将0,0位置的方块设为true（this.grid[i][j] = new MazeGrid(true, 20, 20);），
     * 然后再将j++,此时i=0,j=1，此时不满足上一次的条件，所以将位置在0,1的方块设为false
     * 依照这样类推。最后形成一个相互交错的（彼此true和false的方块不相邻的情况）
     */

    this.grid[0][0].setVisited(true);//将第一个方块设为已经访问
    this.grid[0][0].setPersonCome(true);//将第一个方块设为正在访问
    this.grid[0][0].setStart(true);//将第一个方块设为起点
    this.visited.add("0#0");
    this.grid[(this.rows - 1)][(this.cols - 1)].setEnd(true);//将最后（右下角的）的方块设为终点
    this.grid = createMap(this.grid, 0, 0);
    //调用后面定义的creatMap方法生成一条从起点到终点的路中的一步。接着在createMap中自身调用。


    for (int i = 0; i < this.grid.length; i++) {
      for (int j = 0; j < this.grid[i].length; j++) {
        this.grid[i][j].repaint();//awt.component中的repaint方法是实现控件的重绘
        this.centerPanel.add(this.grid[i][j]);
      }
    }
    this.panel.add(this.northPanel, "North");
    this.panel.add(this.centerPanel, "Center");
  }

  public MazeGrid[][] createMap(MazeGrid[][] mazeGrid, int x, int y)
  {
    int visitX = 0;
    int visitY = 0;
    if ((x - 2 >= 0) &&
      (!mazeGrid[(x - 2)][y].isVisited())) {
      this.willVisit.add(x - 2 + "#" + y);
    }

    if ((x + 2 < this.cols) &&
      (!mazeGrid[(x + 2)][y].isVisited())) {
      this.willVisit.add(x + 2 + "#" + y);
    }

    if ((y - 2 >= 0) &&
      (!mazeGrid[x][(y - 2)].isVisited())) {
      this.willVisit.add(x + "#" + (y - 2));
    }

    if ((y + 2 < this.rows) &&
      (!mazeGrid[x][(y + 2)].isVisited())) {
      this.willVisit.add(x + "#" + (y + 2));
    }

    if (!this.willVisit.isEmpty()) {
      int visit = (int)(Math.random() * this.willVisit.size());
      String id = (String)this.willVisit.get(visit);
      visitX = Integer.parseInt(id.split("#")[0]);
      visitY = Integer.parseInt(id.split("#")[1]);
      mazeGrid[((visitX + x) / 2)][((visitY + y) / 2)].setMark(true);

      mazeGrid[visitX][visitY].setVisited(true);
      if (!this.visited.contains(id)) {
        this.visited.add(id);
      }
      this.willVisit.clear();

      createMap(mazeGrid, visitX, visitY);
    }
    else if (!this.visited.isEmpty()) {
      String id = (String)this.visited.remove(this.visited.size() - 1);
      visitX = Integer.parseInt(id.split("#")[0]);
      visitY = Integer.parseInt(id.split("#")[1]);

      mazeGrid[visitX][visitY].setVisited(true);
      createMap(mazeGrid, visitX, visitY);
    }

    return mazeGrid;
  }

  public String goMaze(MazeGrid[][] mazeGrid, int x, int y)
  {
    int comeX = 0;
    int comeY = 0;

    if ((x - 1 >= 0) &&
      (mazeGrid[(x - 1)][y].isMark()) &&
      (!this.comed.contains(x - 1 + "#" + y))) {
      this.willVisit.add(x - 1 + "#" + y);
    }

    if ((x + 1 < this.cols) &&
      (mazeGrid[(x + 1)][y].isMark()) &&
      (!this.comed.contains(x + 1 + "#" + y))) {
      this.willVisit.add(x + 1 + "#" + y);
    }

    if ((y - 1 >= 0) &&
      (mazeGrid[x][(y - 1)].isMark()) &&
      (!this.comed.contains(x + "#" + (y - 1)))) {
      this.willVisit.add(x + "#" + (y - 1));
    }

    if ((y + 1 < this.rows) &&
      (mazeGrid[x][(y + 1)].isMark()) &&
      (!this.comed.contains(x + "#" + (y + 1)))) {
      this.willVisit.add(x + "#" + (y + 1));
    }

    if (!this.willVisit.isEmpty()) {
      int visit = (int)(Math.random() * this.willVisit.size());
      String id = (String)this.willVisit.get(visit);
      comeX = Integer.parseInt(id.split("#")[0]);
      comeY = Integer.parseInt(id.split("#")[1]);
      mazeGrid[x][y].setPersonCome(false);
      mazeGrid[comeX][comeY].setPersonCome(true);
      mazeGrid[x][y].repaint();
      mazeGrid[comeX][comeY].repaint();
      this.willVisit.clear();
      this.comed.add(x + "#" + y);
    }
    else if (!this.comed.isEmpty()) {
      String id = (String)this.comed.removeLast();
      comeX = Integer.parseInt(id.split("#")[0]);
      comeY = Integer.parseInt(id.split("#")[1]);
      mazeGrid[x][y].setPersonCome(false);
      mazeGrid[comeX][comeY].setPersonCome(true);
      mazeGrid[x][y].repaint();
      mazeGrid[comeX][comeY].repaint();
      this.comed.addFirst(x + "#" + y);
    }

    return comeX + "#" + comeY;
  }

  public void actionPerformed(ActionEvent e)
  {
    if (e.getActionCommand().equals("重新生成迷宫")) {
      refreshMap(this.grid);
    } else if (e.getActionCommand().equals("开始走迷宫")) {
      this.startTime = System.currentTimeMillis();
      this.dostart.setVisible(false);
      this.restart.setText("禁止刷新");
      int delay = 1000;
      int period = 500;
      Timer timer = new Timer();
      timer.scheduleAtFixedRate(new TimerTask() {
        public void run() {
          if (Maze.this.grid[(Maze.this.rows - 1)][(Maze.this.cols - 1)].isPersonCome()) {
            Maze.this.endTime = System.currentTimeMillis();
            JOptionPane.showMessageDialog(null, "已经走出迷宫，耗时" +
              (Maze.this.endTime - Maze.this.startTime) / 1000L + "秒", "消息提示",
              0);
            cancel();
            Maze.this.restart.setText("重新生成迷宫");
          } else {
            String id = Maze.this.goMaze(Maze.this.grid, Maze.this.comeX, Maze.this.comeY);
            Maze.this.comeX = Integer.parseInt(id.split("#")[0]);
            Maze.this.comeY = Integer.parseInt(id.split("#")[1]);
          }
        }
      }
      , delay, period);
    }
  }

  public void refreshMap(MazeGrid[][] mazeGrid)
  {
    this.comeX = 0;
    this.comeY = 0;
    this.willVisit.clear();
    this.visited.clear();
    this.comed.clear();
    remove(this.panel);
    init();
    add(this.panel);
    pack();
    setVisible(true);
  }

  public static void main(String[] args) {
    long start = System.currentTimeMillis();
    new Maze();
    long end = System.currentTimeMillis();
    System.out.println("使用ArrayList生成迷宫耗时：" + (end - start) + "毫秒");
  }
}